package exam.bak.tencent;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class P4 {

    public TreeNode solve(TreeNode root, int[][] b) {
        for (int[] item : b) {
            Map<Integer, TreeNode> map = new HashMap<>();
            if (!isParent(root, new ArrayList<>(), map, item[0], item[1])) {
                if (map.size() < 2) {
                    continue;
                }
                TreeNode node1 = map.get(item[0]);
                TreeNode node2 = map.get(item[1]);
                //1. 值
                int tmp = node1.val;
                node1.val = node2.val;
                node2.val = tmp;
                //左子树
                TreeNode tmpNode = node1.left;
                node1.left = node2.left;
                node2.left = tmpNode;
                //右子树
                tmpNode = node1.right;
                node1.right = node2.right;
                node2.right = tmpNode;
            }
        }
        return root;
    }

    private boolean isParent(TreeNode node, List<Integer> path, Map<Integer, TreeNode> map, int a, int b) {
        if (node == null) {
            return path.contains(a) && path.contains(b);
        } else {
            if (node.val == a || node.val == b) {
                map.put(node.val, node);
            }
            path.add(node.val);
            if (isParent(node.left, path, map, a, b)) {
                return true;
            }
            if (isParent(node.right, path, map, a, b)) {
                return true;
            }
            path.remove(node.val);
        }
        return false;
    }

}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}